#include <algorithm>

using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x)
        : val(x), left(nullptr), right(nullptr)
    {
    }
};

class Solution
{
public:
    int Height(TreeNode* root)
    {
        if (root == nullptr )
        {
            return 0;
        }

        return max(Height(root->left) + 1, Height(root->right) + 1);
    }
    bool isBalanced(TreeNode *root)
    {
        if (root == nullptr)
        {
            return true;
        }

        if (!isBalanced(root->left))
        {
            return false;
        }

        if (!isBalanced(root->right))
        {
            return false;
        }
        int leftHeight = Height(root->left);
        int rightHeight = Height(root->right);

        return abs(leftHeight - rightHeight) < 1;
    }
};
